import { idx2RCB, RCB2Idx } from "../utils";
import { TraceUnit, TraceQueue } from "../types";
import { callbackEliminated, callbackTracing } from "../callbacks";

class Solver {
  private puzzle: number[];
  private unSolvedCells: number[];
  private Vector: number[];

  constructor(puzzle: number[]) {
    if (puzzle.length !== 81) throw new Error("puzzle length must be 81");
    this.puzzle = puzzle;
    this.Vector = new Array(9).fill(0x7ffffff);
    this.unSolvedCells = [];
    for (let i = 0; i < 81; i++) {
      if (puzzle[i] !== 0) {
        this.excludeNum(i, puzzle[i], this.Vector);
      } else {
        this.unSolvedCells.push(i);
      }
    }
  }

  private excludeNum(idx: number, val: number, vector: number[]): void {
    idx2RCB(idx).forEach((prop, idx) => {
      vector[prop] ^= 1 << (val - 1 + idx * 9);
    });
  }

  private getCellVector(idx: number, vector: number[]): number {
    return idx2RCB(idx)
      .map((p) => vector[p])
      .reduce((acc, cur, idx) => acc & (cur >> (idx * 9)));
  }

  public showVector(): void {
    console.log(`Vector length: ${this.Vector.length}`);
    this.Vector.forEach((v) => {
      console.log(v.toString(2).padStart(27, "0").split("").reverse().join(""));
    });
  }

  public solve() {
    const ans = this.traceDown({
      depth: 0,
      vector: [...this.Vector],
      answer: [],
    });
    if (!ans) throw new Error("No solution");
    this.puzzle = [...ans];
  }

  private traceDown(start: TraceUnit): number[] {
    const queue: TraceQueue = [start];
    while (queue.length > 0) {
      const { depth, vector, answer } = queue.pop();
      if (depth === this.unSolvedCells.length) return answer;
      const curIdx = this.unSolvedCells[depth];
      const curVector = this.getCellVector(curIdx, vector);
      if (curVector === 0) {
        callbackEliminated(this, curIdx, answer);
        continue;
      }
      callbackTracing(this, curIdx, answer);
      //根据vector获取当前所有可能的数字
      const candidates = curVector
        .toString(2)
        .split("")
        .reverse()
        .map((bit, idx) => (bit === "1" ? idx + 1 : 0))
        .filter((num) => num !== 0);

      candidates.forEach((candidate) => {
        const newVector = [...vector];
        const newAnswer = [...answer, candidate];
        const newDepth = depth + 1;
        this.excludeNum(curIdx, candidate, newVector);
        queue.push({ depth: newDepth, vector: newVector, answer: newAnswer });
      });
    }
  }

  //验证当前答案是否合法
  private verify(): boolean {
    for (let i = 0; i < 9; i++) {
      const P = new Array(3).fill(0);
      for (let j = 0; j < 3; j++) {
        const idxs = RCB2Idx(i, j);
        for (const idx of idxs) {
          if (this.puzzle[idx] === 0) continue;
          if (P[j] & (1 << (this.puzzle[idx] - 1))) {
            console.log(
              `verify failed at idx: ${idx}, value: ${this.puzzle[idx]}`
            );
            return false;
          }
          P[j] |= 1 << (this.puzzle[idx] - 1);
        }
      }
    }
    return true;
  }

  public get table(): number[] {
    return this.puzzle;
  }
}

export default Solver;
